package leetcode.doublepointer;


import java.util.*;

//15. 三数之和
public class ThreeSum {

    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        System.out.println(threeSumP2(nums));
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
//        if (n<3){
//            return new ArrayList<>();
//        }


        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return res;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int p = i + 1;
            int q = n - 1;
            while (p < q) {

                int sum = nums[p] + nums[q] + nums[i];
                if (sum == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[p]);
                    list.add(nums[q]);

                    res.add(list);
                    while (p < q && nums[p] == nums[p + 1]) {
                        p++;
                    }
                    while (p < q && nums[q] == nums[q - 1]) {
                        q--;
                    }
                    p++;
                    q--;

                } else if (sum < 0) {
                    p++;
                } else {
                    q--;
                }
            }
        }
        return res;
    }


    public static List<List<Integer>> threeSum2(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int p = i + 1;
            int q = n - 1;
            if (nums[i] > 0) {
                return res;
            }
            //跳过重复数据
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            while (p < q) {
                int sum = nums[p] + nums[q] + nums[i];
                if (sum == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[p]);
                    list.add(nums[q]);
                    list.add(nums[i]);
                    res.add(list);

                    while (p < q && nums[p] == nums[p + 1]) {
                        p++;
                    }
                    while (p < q && nums[q] == nums[q - 1]) {
                        q--;
                    }
                    p++;
                    q--;

                } else if (sum > 0) {
                    q--;
                } else {
                    p++;
                }
            }
        }
        return res;
    }

    //暴力---超时
    public static List<List<Integer>> threeSumP(int[] nums) {
        if (nums.length < 3) {
            return new ArrayList<>();
        }

        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {

                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[k]);
                        res.add(list);

                    }
                }

            }
        }
        res.forEach(Collections::sort);
        HashSet<List<Integer>> set = new HashSet<>(res);
        res.clear();
        res.addAll(set);
        return res;
    }


    //双指针---这就类似三指针了
    public static List<List<Integer>> threeSumP2(int[] nums) {
        if (nums.length < 3) {
            return new ArrayList<>();
        }
        //排序
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        //排完序之后有双指针相遇
        for (int i = 0; i < nums.length; i++) {
            //两指针相遇
            int p = i + 1;
            int q = nums.length - 1;
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            if (nums[i] > 0) {
                return res;
            }
            while (p < q) {
                int sum = nums[i] + nums[p] + nums[q];
                if (sum == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[p]);
                    list.add(nums[q]);
                    res.add(list);

                    //跳过重复数据
                    while (p < q && nums[p] == nums[p + 1]) {
                        p++;
                    }
                    while (p < q && nums[q] == nums[q - 1]) {
                        q--;
                    }
                    //两指针后移
                    p++;
                    q--;
                } else if (sum > 0) {
                    //大于0，说明和大了，所以q指针前移
                    q--;
                } else {
                    //小于0，说明和小了，p指针前移
                    p++;
                }
            }
        }
        return res;
    }
}
